package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;


public class LeetCode_day5 {
	
	/**
	 * Given a linked list, swap every two adjacent nodes and return its head.
	 * For example, Given 1->2->3->4, you should return the list as 2->1->4->3
	 * Your algorithm should use only constant space. 
	 * You may not modify the values in the list, only nodes itself can be changed.
	 * @param head
	 */
	public static ListNode swapNodesInPairs(ListNode head){
		//check input valid
		if(head == null) return null;
		if(head.next == null) return head;
		
		ListNode temp, pre = null, pointer = head;
		ListNode newHead = head.next;
		
		while(pointer != null && pointer.next != null){
			temp = pointer.next.next;
			pointer.next.next = pointer;
			if(pre != null) pre.next = pointer.next;
			pointer.next = temp;
			pre = pointer;
			pointer = pointer.next;
		}
		
		return newHead;
	}
	
	/**
	 * ! Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
	 * If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
	 * You may not alter the values in the nodes, only nodes itself may be changed.
	 * Only constant memory is allowed.
	 * For example,
	 * Given this linked list: 1->2->3->4->5
	 * For k = 2, you should return: 2->1->4->3->5
	 * For k = 3, you should return: 3->2->1->4->5
	 * @param head
	 * @param k
	 * @return
	 */
	public static ListNode reverseNodesInKGroup(ListNode head, int k){
		//check input valid
		if(head == null) return null;
		if(!checkValid(head, k)) return null;
		
		ListNode pre = null, begin = head, end = null, after = null;
		ListNode tempPre = null, newHead = head;
		
		int length = k;
		while(length != 1){
			newHead = newHead.next;
			length--;
		}
		
		while(checkValid(begin, k)){
			int num = k;
			tempPre = begin;
			end = begin.next;
			while(num > 1){
				ListNode temp = end.next;
				end.next = begin;
				begin = end;
				end = temp;
				num--;
			}
			tempPre.next = end;
			if(pre != null) {
				pre.next = begin;
			}
			begin = end;
			if(begin != null && begin.next != null) end = begin.next;
			pre = tempPre;
		}
		
		return newHead;
	}
	
	private static boolean checkValid(ListNode node, int k){
		k--;
		while(node != null && node.next != null){
			k--;
			node = node.next;
		}
		if(k > 0) return false;
		else return true;
	}
	
	/**
	 * Given a sorted array, 
	 * remove the duplicates in place such that each element appear only once 
	 * and return the new length.
	 * Do not allocate extra space for another array, 
	 * you must do this in place with constant memory.
	 * @param a
	 * @return
	 */
	public static int removeDupFromeSortedArray(int[] a){
		if(a == null || a.length == 0) return 0;
		
		int newLen = a.length;
		for(int i = 1 ; i < newLen ; i++){
			if(a[i-1] == a[i]){//move a[i] to the tail
				newLen--;
				int temp = a[i];
				for(int j = i ; j < newLen ; j++)
					a[j] = a[j+1];
				a[newLen] = temp;
			}
		}
		return newLen;
	}
	
	/**
	 * 
	 * @param a
	 * @param val
	 * @return
	 */
	public static int removeElement(int[] a, int val){
		if(a == null || a.length == 0) return 0;
		
		int newLen = a.length;
		for(int i = 0 ; i < newLen ; i++){
			if(a[i] == val){
				newLen--;
				for(int j = i ; j < newLen ; j++){
					a[j] = a[j+1];
				}
			}
		}
		return newLen;
	}
	
	public static int strStr(String str, final String target){
		
		return 0;
	}
	
	/**
	 * !Implement integer division without using /, % and *
	 * Analysis:
	 * We can use -, +, >>, <<
	 * If we use - only, it's time-consuming, especially b is much smaller
	 * than a such as: a = 1234567789, b = 1
	 * 
	 * 1. Keep  multiply 2 (<<1) to the divisor, 
	 * until it is greater than the dividend. Store the times of shift operation.
	 * 2. if dividend > divisor, then dividend = dividend - divisor/2(>>1). 
	 * Until dividend< original divisor. Store the   result.
     * 3. Output the result.
	 * @param a
	 * @param b
	 * @return
	 */
	public static int divide(int a, int b){
		if(a < b) return 0;
		
		int temp = b;
		int result = 0;
		while(a >= b){
			int temp1 = 1;
			while(a >= temp) {
				temp = temp << 1;
				temp1 = temp1 << 1;
			}
			a -= temp >> 1;
			result += (temp1 >> 1);
			temp = b;
		}
		return result;
	}
	
	/**
	 * You are given a string, S, and a list of words, L, 
	 * that are all of the same length. Find all starting indices of substring(s) 
	 * in S that is a concatenation of each word in L exactly once 
	 * and without any intervening characters.
	 * For example, given:
	 * S: "barfoothefoobarman"
	 * L: ["foo", "bar"]
	 * You should return the indices: [0,9].
	 * @param s
	 * @param l
	 * @return
	 */
	public static List<Integer> subStrWithConcatenationOfAllWords(String s, String[] l){
		if(s == null || l == null) return null;
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for(String str : l) map.put(str.intern(), 0);
		int ind = 0, len = l[0].length(), num = 0;
		boolean flag = false;
		List<Integer> res = new ArrayList<Integer>();
		
		while(ind < s.length() && ind+len <= s.length()){
			String subs = s.substring(ind, ind+len).intern();
			if(map.containsKey(subs)){
				flag = true;
				int temp = map.get(subs);
				map.put(subs, ++temp);
				num = temp;
			}else{
				if(!flag) {
					ind++;
					continue;
				}
		        flag = false;
				//check number
				boolean oneturn = true;
				Iterator<Entry<String, Integer>> itera = map.entrySet().iterator();
				while(itera.hasNext()){
					if(itera.next().getValue() != num){
						oneturn = false;
						break;
					}
				}
				if(oneturn) res.add(ind-len*l.length);
				else{
					num--;
					Iterator<String> itera1 = map.keySet().iterator();
					while(itera1.hasNext()){
						map.put(itera1.next(), num);
					}
				}
			}
			ind += len;
		}
		return res;
	}
	
	/**
	 * ! Step 1: Find the largest index k, such that A[k]<A[k+1]. 
	 * If not exist, this is the last permutation. 
	 * (in this problem just sort the vector and return.)
	 * Step 2: Find the largest index l, such that A[l]>A[k].
	 * Step 3: Swap A[k] and A[l].
	 * Step 4: Reverse A[k+1] to the end
	 * @param a
	 * @return
	 */
	public static int[] nextPermutation(int[] a){
		if(a == null || a.length < 2) return null;
 		
		int k = -1, i;
		for(i = 0 ; i < a.length-1 ; i++){
			if(a[i] < a[i+1]) k = i;
		}
		
		if(k == -1) {
			Arrays.sort(a);
			return a;
		}
		
		for(i = a.length - 1 ; i >= 0 ; i--)
			if(a[i] > a[k]) break;
		//swap a[k] and a[i]
		a[k] += a[i];
		a[i] = a[k] - a[i];
		a[k] = a[k] - a[i];
		//reverse a[k+1] to the end
		LinkedList<Integer> stack = new LinkedList<Integer>();
		for(int j = k+1 ; j < a.length ; j++) stack.add(a[j]);
		for(int j = k+1 ; j < a.length ; j++) a[j] = stack.pollLast();
		
		return a;
	}

	/**
	 * Dynamic Programming
	 * @param str
	 * @return
	 */
	public static String longestValidParentheses(String str){
		//check input valid
		if(str == null || str.length() < 2) return null;
		
		int[] indexes = new int[2];
		Arrays.fill(indexes, -1);
		boolean[][] valid = new boolean[str.length()][str.length()];
		for(int i = 0 ; i < str.length() ; i++) Arrays.fill(valid[i], false);
		char[] s = str.toCharArray();
		//find all base-case
		for(int i = 0 ; i < s.length-1 ; i++) {
			if(s[i] == '(' && s[i+1] == ')'){
				valid[i][i+1] = true;
				if(indexes[0] != -1){
					indexes[0] = i;
					indexes[1] = i+1;
				}
				i++;
			}
		}
		//induction
		for(int num = 2 ; num <= s.length / 2; num++){//
			//for all num-1 valid ones
			for(int i = 0 ; i < s.length-num*2 ; i++){
				int end = i+(num-1)*2-1;
				if(valid[i][end]){
					//condition one  "(old)"
					int newbegin = i-1, newend = end+1;
					if(newbegin >= 0 && newend < s.length && s[newbegin] =='(' && s[newend] == ')'){
						valid[newbegin][newend] = true;
						indexes[0] = newbegin;
						indexes[1] = newend;
					}else{
						//condition two "old1()" or "()old"
						int left = i-1;
						int right = end+1;
						if(left > 0 && valid[left-1][left]) {
							valid[left-1][end] = true;
							indexes[0] = left-1;
							indexes[1] = end;
						}
						else if(right < s.length-1 && valid[right][right+1]) {
							valid[i][right+1] = true;
							indexes[0] = i;
							indexes[1] = right+1;
						}
					}	
				}
			}
		}
		return str.substring(indexes[0], indexes[1]+1);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode head = new ListNode(1);
		ListNode pointer = head;
		for(int i = 2 ; i < 6 ; i++){
			pointer.next = new ListNode(i);
			pointer = pointer.next;
		}
		//System.out.println(checkValid(head, 5));
		//ListNode newHead = swapNodesInPairs(head);
		
		ListNode newHead = reverseNodesInKGroup(head,3);
		int[] a = new int[]{1,2,2,3,3,4,5,6,6};
		System.out.println(removeDupFromeSortedArray(a));
		System.out.println(removeElement(a,3));
		System.out.println(divide(1234,5));
		List<Integer> list = subStrWithConcatenationOfAllWords("barfoothefoobarman", new String[]{"foo", "bar"});
		a = new int[]{1,4,3,2,5};
		nextPermutation(a);
		System.out.println(longestValidParentheses(")(()()))()"));
		System.out.println();
	}
}
/**
 * Single linked list
 * @author hangou
 *
 * @param <T>
 */
class ListNode<T extends Number>{
	T val;
	ListNode<T> next;
	
	public ListNode(T val){
		this.val = val;
		this.next = null;
	}
}
/**
 * if(map.entrySet().iterator().hasNext()) map.entrySet().iterator().next();//is wrong
 * 
 * Iterator<Entry<String, Integer>> itera = map.entrySet();//is correct
 * if(itera.hasNext()) itera.next();//is correct
 */